|
Nearest neighbor search (NNS), also known as proximity search, similarity search or closest point search, is an optimization problem for finding closest (or most similar) points. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values. Formally, the nearest-neighbor (NN) search problem is defined as follows: given a set ''S'' of points in a space ''M'' and a query point ''q'' ∈ ''M'', find the closest point in ''S'' to ''q''. Donald Knuth in vol. 3 of ''The Art of Computer Programming'' (1973) called it the post-office problem, referring to an application of assigning to a residence the nearest post office. A direct generalization of this problem is a ''k''-NN search, where we need to find the ''k'' closest points. Most commonly ''M'' is a metric space and dissimilarity is expressed as a distance metric, which is symmetric and satisfies the triangle inequality. Even more common, ''M'' is taken to be the ''d''-dimensional vector space where dissimilarity is measured using the Euclidean distance, Manhattan distance or other distance metric. However, the dissimilarity function can be arbitrary. One example are asymmetric Bregman divergences, for which the triangle inequality does not hold. ==Applications== The nearest neighbor search problem arises in numerous fields of application, including: *Pattern recognition - in particular for optical character recognition *Statistical classification- see k-nearest neighbor algorithm *Computer vision *Computational geometry - see Closest pair of points problem *Databases - e.g. content-based image retrieval *Coding theory - see maximum likelihood decoding *Data compression - see MPEG-2 standard *Robotic sensing〔Bewley, A., & Upcroft, B. (2013). Advantages of Exploiting Projection Structure for Segmenting Dense 3D Point Clouds. In Australian Conference on Robotics and Automation ()〕 *Recommendation systems, e.g. see Collaborative filtering *Internet marketing - see contextual advertising and behavioral targeting *DNA sequencing *Spell checking - suggesting correct spelling *Plagiarism detection *Contact searching algorithms in FEA *Similarity scores for predicting career paths of professional athletes. *Cluster analysis - assignment of a set of observations into subsets (called clusters) so that observations in the same cluster are similar in some sense, usually based on Euclidean distance *Chemical similarity *Sampling-Based Motion Planning 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「nearest neighbor search」の詳細全文を読む スポンサード リンク
|